package com.caoyanan.algorithm.question.zuoTraining.training004.class01;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

import java.util.Arrays;

/**
 * 给定一个数组arr，从左到右表示昨天从早到晚股票的价格
 * 作为一个事后诸葛亮，你想知 道如果交易次数不超过K次，
 * 且每次交易只买卖一股，返回能挣到的最大钱数
 * @author: caoyanan
 * @time: 2021/5/26 22:16
 */
public class Question03_MaxProfit3 {

    public static void main(String[] args) {

        int count = 10000;
        int k = 3;
        for (int i = 0; i < count; i++) {
            int[] arr = LogarithmInputGenerator.getInstance().generateRandomArray(10, 10);
            int money = maxProfit(arr, k);
            System.out.printf("价格 %s 最多交易 %s 次可以得到的最高收益为 %s \n", Arrays.toString(arr), k, money);
        }

    }

    private static int maxProfit(int[] arr, int k) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        if (k >= arr.length / 2) {
            return Question02_MaxProfit2.maxProfit(arr);
        }

        /**
         * dp[i][j]表示0到i位置的股票价格，使用j次，能够获取的最高收益
         * 首先第一行，只有0位置的股票，使用j次，得到的收益是0 dp[0][j] = 0;
         * 第一列，有0~i位置的股票，只能用0次 dp[i][0] = 0;
         * 对于一个普遍位置dp[i][j]。首先第一种情况，位置i的股票根本不参与交易，所以dp[i][j] = dp[i-1][j]
         * 然后第二种情况，arr[i]参与交易，这里有一个贪心算法，想要使dp[i][j]达到最大收益，arr[i]必须参与的是最后一次的卖出。论证：arr[i]位置买在卖，收益是0，没任何意义
         * 当最后一次是i位置卖出的时候，买入可能是前面的任何一个位置，即max(dp[i-1][j-1]+arr[i]-arr[i-1], dp[i-2][j-1]+arr[i]-arr[i-2], dp[i-3][j-1]+arr[i]-arr[i-3], ... dp[0][j-1]+arr[i]-arr[0])
         * 也就是 max(dp[i-1][j-1]-arr[i-1], dp[i-2][j-1]-arr[i-2], dp[i-3][j-1]-arr[i-3],... dp[0][j-1]-arr[0]) + arr[i]
         *
         * 再观察dp[i-1][j]。首先i-1不参与交易，dp[i-1][j]=dp[i-2][j]
         * 然后i-1参与卖出。买入的位置就是max(dp[i-2][j-1]-arr[i-2], dp[i-3][j-1]-arr[i-3], ...dp[0][j-1]-arr[0]) + arr[i-1]
         * 所以，那个遍历求最大值 dp[k][j-1]-arr[k]有重复计算，假如 dp[i-1][j]第二种情况得到的那个值是 max(...) = t。 那么dp[i][j]第二种情况的值就是 max(dp[i-1][j-1]-arr[i-1], t)+arr[i]
         * 所以，维护好这个t的值，就省略了二维表每次都向当前列向上遍历寻找max的过程，所以这个二维表需要一列一列的来填
         */
        int[][] dp = new int[arr.length][k+1];

        for (int j = 1; j <= k; j++) {
            int t = dp[0][j-1] - arr[0];
            for (int i = 1; i < arr.length; i++) {
                t = Math.max(t, dp[i - 1][j - 1] - arr[i-1]);
                dp[i][j] = Math.max(dp[i - 1][j], t + arr[i]);
            }
        }
        return dp[arr.length-1][k];
    }
}
